package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/kth-distinct-string-in-an-array/'>数组中第 K 个独一无二的字符串(Kth Distinct String in an Array)</a>
 * <p>独一无二的字符串 指的是在一个数组中只出现过 一次 的字符串。</p>
 * <p>给你一个字符串数组 arr 和一个整数 k ，请你返回 arr 中第 k 个 独一无二的字符串 。如果 少于 k 个独一无二的字符串，那么返回 空字符串 "" 。</p>
 * <p>注意，按照字符串在原数组中的 顺序 找到第 k 个独一无二字符串。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入：arr = ["d","b","c","b","c","a"], k = 2
 *      输出："a"
 *      解释：
 *          arr 中独一无二字符串包括 "d" 和 "a" 。
 *          "d" 首先出现，所以它是第 1 个独一无二字符串。
 *          "a" 第二个出现，所以它是 2 个独一无二字符串。
 *          由于 k == 2 ，返回 "a" 。
 *
 * 示例 2:
 *      输入：arr = ["aaa","aa","a"], k = 1
 *      输出："aaa"
 *      解释：
 *          arr 中所有字符串都是独一无二的，所以返回第 1 个字符串 "aaa" 。
 *
 * 示例 3：
 *      输入：arr = ["a","b","a"], k = 3
 *      输出：""
 *      解释：
 *          唯一一个独一无二字符串是 "b" 。由于少于 3 个独一无二字符串，我们返回空字符串 "" 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= k <= arr.length <= 1000</li>
 *     <li>1 <= arr[i].length <= 5</li>
 *     <li>arr[i] 只包含小写英文字母。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/19 9:30
 */
public class LC2053KthDistinctStringInArray_S {

    static class Solution {
        public String kthDistinct(String[] arr, int k) {
            Map<String, Integer> visited = new HashMap<>();
            for (String str : arr) {
                visited.put(str, visited.getOrDefault(str, 0)+1);
            }
            for (String str : arr) {
                if (visited.get(str) == 1) {
                    --k;
                }
                if (k == 0) {
                    return str;
                }
            }
            return "";
        }

        public String kthDistinct2(String[] arr, int k) {
            Map<String, Boolean> visited = new HashMap<>();
            for (String str : arr) {
                if (visited.containsKey(str)) {
                    visited.put(str, true);
                } else {
                    visited.put(str, false);
                }
            }
            for (String str : arr) {
                if (!visited.get(str)) {
                    --k;
                }
                if (k == 0) {
                    return str;
                }
            }
            return "";
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.kthDistinct(new String[]{"d", "b", "c", "b", "c", "a"}, 2));
        System.out.println(solution.kthDistinct(new String[]{"aaa", "aa", "a"}, 1));
        System.out.println(solution.kthDistinct(new String[]{"a", "b", "a"}, 3));
    }
}
